package com.example.dynamicprogramming41;

/**
 * @description 动态规划-状态转移表法
 * @auther lijiewei
 * @date 2022/4/9 17:32
 */
public class DynamicProgramming {



    /**
     * 求最短路径（状态转移表法）
     * @param matrix 路径权重数组
     * @param n 数组行列长度
     * @return
     * @author lijiewei
     * @date   2022/4/12 17:46
     */
    public int minDistDP(int[][] matrix, int n) {
        int[][] states = new int[n][n];
        int sum = 0;
        //初始化states的第一行数据
        for (int j = 0; j < n; j++) {
            sum += matrix[0][j];
            states[0][j] = sum;
        }

        sum = 0;
        //初始化states的
        for (int i = 0; i < n; i++) {
            sum += matrix[i][0];
            states[i][0] = sum;
        }

        //递推状态表中的状态
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; ++j) {
                states[i][j] = matrix[i][j] + Math.min(states[i][j-1], states[i-1][j]);
            }
        }
        return states[n-1][n-1];
    }


}
